COCI/2009-2010/Contest #7 - 24.04.2010/bakice/bakice.cpp

   1 #include <iostream>
   2 #include <vector>
   3 #include <cassert>
   4
   5 #define D(x) cout << #x " = " << (x) << endl
   6 using namespace std;
   7
   8 const int MAXN = 105;
   9
  10 int dist(int x1, int y1,    int x2, int y2){
  11   int dx = x1 - x2;
  12   int dy = y1 - y2;
  13   return dx * dx + dy * dy;
  14 }
  15
  16
  17 char mat[MAXN][MAXN];
  18 int sits[MAXN];
  19 typedef pair<int, int> point;
  20
  21 int rows, cols;
  22 vector<point> people, chairs;
  23
  24 int someoneCloser(int guy, int chair){
  25   int D = dist(people[guy].first, people[guy].second, chairs[chair].first, chairs[chair].second);
  26   for (int i = 0; i < people.size(); ++i){
  27     if (i == guy) continue;
  28     int d = dist(people[i].first, people[i].second, chairs[chair].first, chairs[chair].second);
  29     if (d < D) return true;
  30   }
  31   return false;
  32 }
  33
  34 int main(){
  35   cin >> rows >> cols;
  36   for (int i = 0; i < rows; ++i){
  37     for (int j = 0; j < cols; ++j){
  38       cin >> mat[i][j];
  39       if (mat[i][j] == 'X') people.push_back(point(i, j));
  40       if (mat[i][j] == 'L') chairs.push_back(point(i, j));
  41     }
  42   }
  43
  44   for (int i = 0; i < people.size(); ++i){
  45     //figure out in what chair this guy sits
  46     vector<pair<int, int> > options;
  47     for (int j = 0; j < chairs.size(); ++j){
  48       options.push_back(make_pair(dist(people[i].first, people[i].second, chairs[j].first, chairs[j].second), j));
  49     }
  50     sort(options.begin(), options.end());
  51     sits[i] = -1; //no chair, yet
  52     for (int j = 0; j < options.size(); ++j){
  53       if (someoneCloser(i, j)) continue;
  54       else{
  55         sits[i] = options[j].second;
  56         break;
  57       }
  58     }
  59   }
  60
  61   for (int i = 0; i < people.size(); ++i){
  62     cout << sits[i] << endl;
  63   }
  64
  65   return 0;
  66 }